#include "c_skip_list.h"

SKLNode* ConstructSKLNode()
{
    SKLNode* node = (SKLNode*)malloc(sizeof(SKLNode));
    node->right = NULL;
    node->next = NULL;
    return node;
}

void DestructSKLNode(SKLNode* node)
{
    if(!node) return ;
    node->right = NULL;
    node->next = NULL;
    free((void*)node);
}

SkipList* ConstructSkipList()
{
    SkipList* sp = (SkipList*)malloc(sizeof(SkipList));
    sp->head = NULL;
    sp->level = 0;
    sp->size = 0;
    return sp;
}

void DestructSkipList(SkipList* sp)
{
    if(!sp || !sp->head || sp->level == 0) return;
    SKLNode* cur = sp->head;
    while(cur)
    {
        SKLNode* nxt = cur->next;
        while(cur)
        {
            SKLNode* rgh = cur->right;
            DestructSKLNode(cur);
            cur = rgh;
        }
        cur = nxt;
    }
    sp->head = NULL;
    sp->level = 0;
    free((void*)sp);
}

unsigned int GetSkipListDepth(SkipList* sp)
{
    return sp ? sp->level : 0;
}

unsigned int GetSkipListSize(SkipList* sp)
{
    return sp ? sp->size : 0;
}

bool Search(SkipList* sp,int key)
{
    if(!sp) return false;
    SKLNode* cur = sp->head;
    while(cur)
    {
        while(cur->right && cur->right->key < key)
        {
            cur = cur->right;
        }
        if(!cur->right || cur->right->key > key)
        {
            cur = cur->next;
        }
        else 
        {
            return true;
        }
    }
    return false;
}

void Add(SkipList* sp,int key)
{
    if(!sp) return ;
    SKLNode* cur = sp->head;
    Array* array = ConstructArray(sp->level+1);
    
    //find key path
    while(cur)
    {
        while(cur->right && cur->right->key < key)
        {
            cur = cur->right;
        }
        PushBack(array,(void*)cur);
        cur = cur->next;
    }

    bool bInsert = true;
    SKLNode* nxt = NULL;
    while(bInsert && !Empty(array))
    {
        SKLNode* back = (SKLNode*)Back(array);
        PopBack(array);
        SKLNode* node = ConstructSKLNode();
        node->right = back->right;
        node->next = nxt;
        node->key = key;
        back->right = node;
        bInsert = (rand()%2) == 0;
        nxt = node;
    }
    if(bInsert)
    {
        ++sp->level;
        SKLNode* rgh = ConstructSKLNode();
        rgh->key = key;
        rgh->right = NULL;
        rgh->next = nxt;

        //empty node
        SKLNode* dummy = ConstructSKLNode();
        dummy->key = -1;
        dummy->next = sp->head;
        dummy->right = rgh;
        sp->head = dummy;
    }
    DestructArray(array);
    ++sp->size;
}

bool Erase(SkipList* sp,int key)
{
    if(!sp || !sp->head) return false;
    SKLNode* cur = sp->head;
    bool bErase = false;
    while(cur)
    {
        while(cur->right && cur->right->key < key)
        {
            cur = cur->right;
        }
        //remove key
        if(cur->right && cur->right->key == key)
        {
            SKLNode* tmp = cur->right->right;
            DestructSKLNode(cur->right);
            cur->right = tmp;
            cur = cur->next;
            bErase = true;
        }
        else
        {
            cur = cur->next;
        }
    }
    if(bErase) --sp->size;
    return bErase;
}
